package com.zzz.offer.votecount;

public class VoteItemMax {


    // 如果一个数组 中 有一个数字 个数超过了半数，那么就可以使用投票法
    // 投票法充分利用了 超过一半 这条件       不过还有的办法是先排序，然后再直接找中间的元素，这个排序就不是O(n) 复杂度了
    // 只要 数组的元素 超过半数，最极端的情况下，除了这个元素，数组中就只有另外一个元素
    // 那么不相同的元素 个数 相互抵消 那么一定剩下超过半数的元素
    // 这就是为什么可以使用投票法
    // 步骤：
    // 1. 设置计数器 count
    // 2. 设置候选元素，
    // 3. 拿 array[0] 当做候选元素 从0 开始 遍历 array
    // 4. 遍历时候遇到 与候选相同的元素就 count + 1,  遇到不同的元素count -1
    // 5. 如果count < 0  这是后就直接拿当前的元素作为 候选元素
    // 6. 继续遍历
    // 7. 最终结果是：除了超过半数个数的那个元素，其他元素都会被抵消掉，剩下的就是 超过半数的数字了
    //
    // 复杂度 O(n)  只需要两个变量  空间复杂度 O(1)
    public int MoreThanHalfNum_Solution(int[] array) {
        //投票法：
        int votes = 0;
        int x = 0;

        for (int num : array) {
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }

}
